package com.sx.sx1.lintcode.day717;

import java.util.*;


public class LC286 {

    static class Solution {
        /**
         * @param n:     describe the size of an array
         * @param nums:  A sequence of 2^n numbers
         * @param query: the number of m inquiries
         * @return: Returns a list of the number of inversions after each change
         */
        public List<Long> inversions(int n, int[] nums, int[] query) {
            // 归并排序
            List<Long> ans =new ArrayList<>();
            int size = nums.length;
            int[] help = new int[size];
            for (int pow : query) {
                int  rn = (int)Math.pow(2,pow);
                for (int i = 0; i <size ; i+=rn) {
                   int L=i;
                   int R = i+rn-1;

                   while (L<=R){ //翻转
                       int t = nums[L];
                       nums[L] = nums[R];
                       nums[R] = t;
                       help[L] = nums[L];
                       help[R] = nums[R];

                       L++;
                       R--;
                   }
                }

                ans.add(guibing(help));
            }
            return ans;
        }

        public Long guibing(int[] arr) {
            long[] cnt = {0};
            int step = 1;
            int size = arr.length;
            while (step < size) {
                int L = 0;
                while (L < size) {
                    int M = L + step - 1; //左组结束位置
                    if (M > size) break;
                    int R = Math.min(M + step, size - 1); //右组结束位置
                    merge(arr, L, M, R, cnt);
                    L = R + 1; //下一组继续
                }

                if(step > size/2) break;
                step*=2;
            }
            return cnt[0];
        }

        public void merge(int[] arr, int l, int m, int r, long[] cnt) {
            int[] help = new int[r - l + 1];
            int i = 0;
            int p1 = l;
            int p2 = m+1;
            while (p1 <= m && p2 <= r) {
                if (arr[p1] <= arr[p2]) {
                    help[i++] = arr[p1++];
                } else {
                    cnt[0]+= m-p1+1;
                    help[i++] = arr[p2++];
                }
            }

            while (p1 <= m) {
                help[i++] = arr[p1++];
            }
            while (p2 <= r) {
                help[i++] = arr[p2++];
            }

            for (int j = 0; j <help.length ; j++) {
                arr[l+j] = help[j];
            }
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        List<Long> inversions = obj.inversions(2, new int[]{2, 1, 4, 3}, new int[]{1, 2, 0, 2});
        System.out.println(inversions);
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有176条未读消息，请及时查看
286 · 逆序对
算法
困难
通过率
44%

题目
题解3
笔记
讨论1
排名
记录
描述
给定一个n，一个包含2^n个数的数列。再给定一个包含m个数的数组，表示询问m次，对于每个qi，每次要求把这些数每2^qi分为一组，然后把每组进行翻转。每次操作后整个序列中的逆序对个数是多少呢？
例如:
对于序列1 3 4 2，逆序对有(4, 2),(3, 2),总数量为2。
翻转之后为2 4 3 1，逆序对有(2, 1),(4, 3), (4, 1), (3, 1),总数量为4。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


0
≤
n
≤
20
0≤n≤20
1
≤
m
≤
1
0
5
1≤m≤10
5

0
≤
q
i
≤
n
0≤q
i
​
 ≤n

样例
样例 1:

输入:
2
[2,1,4,3]
4
[1,2,0,2]
输出:
[0,6,6,0]
说明：
初始序列2 1 4 3
2^q1 = 2 -> 第一次：1 2 3 4 -> 逆序对数为0
2^q2 = 4 -> 第二次：4 3 2 1 -> 逆序对数为6
2^q3 = 1 -> 第三次：4 3 2 1 -> 逆序对数为6
2^q4 = 4 -> 第四次：1 2 3 4 -> 逆序对数为0
相关知识
学习《算法求职课——百题精讲》课程中的25.1逆序对-视频讲解相关内容 ，了解更多相关知识！
标签
企业
腾讯
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
已开启智能提示
发起考试
45 分 00 秒
1234567891011
public class Solution {
    /**
     * @param n: describe the size of an array
     * @param nums: A sequence of 2^n numbers
     * @param query: the number of m inquiries
     * @return: Returns a list of the number of inversions after each change

public List<Long> inversions(int n, int[] nums, int[] query) {
    // write your code here
}
}
控制台
        历史提交

 */
